/*
 * @Author: szx
 * @Date: 2021-10-27 11:44:55
 * @LastEditTime: 2021-10-27 13:15:57
 * @Description:
 * @FilePath: \leetcode\189\189.go
 */
package main

func rotate(nums []int, k int) {
	n := len(nums)
	k %= n
	// 最外面的循环为最小公约数的次数，也就是循环到原点的次数
	for start, count := 0, gcd(k, n); start < count; start++ {
		// cur此轮次数的起点
		pre, cur := nums[start], start
		for ok := true; ok; ok = cur != start {
			next := (cur + k) % n
			nums[next], pre, cur = pre, nums[next], next
		}
	}
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func main() {
	// a, b := 3, 1
	// a, b = b, a
	// print(a, b)
	// print(gcd(6, 2))

	rotate([]int{1, 2, 3, 4, 5, 6}, 3)
}
